FLOW4 魔术球问题

模型：

有向无环图最小路径覆盖->网络最大流

题意：

假设有 n 根柱子，按下述规则在这 n 根柱子中依次放入编号为 1,2,3,4,⋯ 的球：每次只能在某根柱子的最上面放球；在同一根柱子中，任何 2 个相邻球的编号之和为完全平方数。 试计算出在 n 根柱子上最多能放多少个球。

题解：

又是一道假网络流题

如果是网络流做法的话，应该是将每个球看成点，把符合条件的“关系”看成有向边，跑一遍有向无环图最小路径覆盖（方法见FLOW3 最小路径覆盖问题）

但我选择了贪心来解决这题（主要是代码方便，懒得去搞网络流了。。。）

假设能放m个球，贪心思路就是对于1..m每个球，枚举每根柱子，能放就放，不能放新开一个，直到柱子开完为止

显然的，复杂度$O(nm)$

贪心正确性不会证，暂时也看不懂，但可以先放出两个版本的证明：

版本一，版本二

另外，其实m的值也是可以$O(1)$计算的

具体的通项公式可以见OEIS A047838（反正我也不会证。。。）

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

vector<int> ans[60];
int n,m;

bool check(int x){
    return (int)sqrt(x)*(int)sqrt(x)==x;
}

signed main(){
    read(n);
    m=(n+1)*(n+1)/2-1;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(ans[j].empty()||check(ans[j][ans[j].size()-1]+i)){
                ans[j].push_back(i);
                break;
            }
    write(m);
    for(int i=1;i<=n;i++){
        puts("");
        for(int j=0;j<ans[i].size();j++){
            write(ans[i][j]);
            if(j!=ans[i].size()-1) putchar(' ');
        }
    }
}